// https://leetcode.cn/problems/basic-calculator-ii/description/

// 算法思路总结：
// 1. 栈思想处理基本计算器问题（含加减乘除）
// 2. 遍历字符串，处理空格、数字和运算符
// 3. 遇到数字时解析完整数字，根据前序运算符入栈
// 4. 加减法直接入栈正负数，乘除法立即计算栈顶元素
// 5. 最后累加栈中所有元素得到结果
// 6. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    int calculate(string s) 
    {
        int m = s.size();
        int i = 0;
        char op = '+';
        vector<int> st;

        while (i < m)
        {
            if (s[i] == ' ')
            {
                i++;
            }
            else if (isdigit(s[i]))
            {
                int tmp = 0;
                while (i < m && isdigit(s[i]))
                {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                
                if (op == '+')
                {
                    st.push_back(tmp);
                }
                else if (op == '-')
                {
                    st.push_back(-tmp);
                }
                else if (op == '*')
                {
                    st.back() *= tmp;
                }
                else if (op == '/')
                {
                    st.back() /= tmp;
                }
            }
            else
            {
                op = s[i];
                i++;
            }
        }

        int ret = 0;
        for (const int& num : st)
        {
            ret += num;
        }

        return ret;
    }
};

int main()
{
    string s1 = "3+2*2", s2 = " 3+5 / 2 ";
    Solution sol;

    cout << sol.calculate(s1) << endl;
    cout << sol.calculate(s2) << endl;

    return 0;
}